package com.ryujung.linked_list.leetCode_141;

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }

    ListNode(int x, ListNode next) {
        val = x;
        this.next = next;
    }

    ListNode(int... arr) {
        this.val = arr[0];
        ListNode before = this;
        for (int i = 1; i < arr.length; i++) {
            ListNode cur = new ListNode(arr[i]);
            before.next = cur;
            before = cur;
        }
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

/*
Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which
 represents the position (0-indexed) in the linked list where tail connects to.
If pos is -1, then there is no cycle in the linked list.
*/

/**
 * 循环链表检测
 * <p>
 * 思路:快慢双指针
 * 设置两个指针,步长分别为1和2
 * 让两个指针分别从heaad和head.next遍历链表,
 * 如果两指针相遇,说明存在circle,返回true
 * 如果步长为2的指针遍历到null值,则返回false;
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;

        //循环终止条件是slow==fast或者fast==null
        while (slow != fast && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (slow == fast) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 2023年02月01日16:05:17追加
     * 思路：
     * 判断链路中是否有环的存在，可以使用双指针法，
     * 如果慢指针追上快指针，则说明有环。
     * 否则遍历到链表尾部结束
     */
    public static boolean hasCycle2(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next;
            if (fast == slow) return true;
            slow = slow.next;

            fast = fast.next;
            if (fast == slow) return true;
        }
        return false;
    }
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)

    public static void main(String[] args) {
        ListNode originNode = new ListNode(3, 2, 0, 4);
        ListNode node = new ListNode(3, 2, 0, 4);
        int pos = -1;

        ListNode tail = node;
        while (tail.next != null) {
            tail = tail.next;
        }

        if (pos > 0) {
            ListNode cutPoint = null;
            for (int i = 0; i < pos; i++) {
                cutPoint = node.next;
            }
            tail.next = cutPoint;
        }
        System.out.println("current Node:" + originNode + ",pos = " + pos);
        System.out.println("hasCycle? ");
        System.out.println(hasCycle2(node));
    }
}